package _2022.hot100._312_戳气球;

import java.util.Arrays;

/**
 * @author： YHSimon
 * @date： 2022-05-28 10:15
 */
public class Solution {

    public int[][] rec;
    public int[] val;
    //记忆化搜索 108 ms
    public int maxCoins3(int[] nums){
        int n=nums.length;
        val=new int[n+2];
        val[0]=val[n+1]=1;
        System.arraycopy(nums, 0, val, 1, n);
        rec=new int[n+2][n+2];
        for(int i=0;i<=n+1;i++){
            Arrays.fill(rec[i],-1);
        }
        return solve(0,n+1);
    }

    private int solve(int left, int right) {
        if(left>=right-1){
            return 0;
        }
        if(rec[left][right]!=-1){
            return rec[left][right];
        }
        for(int i=left+1;i<right;i++){
            int sum=val[left]*val[i]*val[right];
            sum+=solve(left,i )+solve(i, right);
            rec[left][right]=Math.max(rec[left][right],sum);
        }
        return rec[left][right];
    }

    // 动态规划 35 ms
    /*public int maxCoins2(int[] nums){
        int n=nums.length;
        int[][] rec=new int[n+2][n+2];
        int[] val=new int[n+2];
        val[0]=val[n+1]=1;
        System.arraycopy(nums, 0, val, 1, n);
        for(int i=n-1;i>=0;i--){
            for(int j=i+2;j<=n+1;j++){
                for(int k=i+1;k<j;k++){
                    int sum=val[i]*val[k]*val[j];
                    sum+=rec[i][k]+rec[k][j];
                    rec[i][j]=Math.max(rec[i][j],sum);
                }
            }
        }
        return rec[0][n+1];
    }*/

    // 回溯  超时
    public int maxCoins(int[] nums) {
        int[] visited = new int[nums.length];
        int[] max=new int[1];
        max[0]=Integer.MIN_VALUE;
        dfs(nums, visited, 0, 0,max);
        return max[0];
    }

    private void dfs(int[] nums, int[] visited, int tmpMax, int count,int[] max) {
        if (count == nums.length) {
            max[0] = Math.max(max[0], tmpMax);
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 0) {
                int left = 1,right=1;
                int tmp = i - 1;
                while (tmp >= 0) {
                    if (visited[tmp] == 0) {
                        left = nums[tmp];
                        break;
                    }
                    tmp--;
                }
                tmp=i+1;
                while (tmp < nums.length) {
                    if (visited[tmp] == 0) {
                        right = nums[tmp];
                        break;
                    }
                    tmp++;
                }

                tmpMax += left * right * nums[i];
                visited[i] = 1;
                dfs(nums, visited, tmpMax, count + 1,max);
                visited[i] = 0;
                tmpMax -= left * right * nums[i];
            }

        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        // System.out.println(s.maxCoins(new int[]{3, 1, 5, 8}));
        System.out.println(s.maxCoins(new int[]{ 1, 5}));
    }

}
